#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1e5 + 10, M = 2 * N, K = 1e3 + 10;
int h[N], e[M], ne[M], idx;
int q[N], d[N];
bool st[N];
int g[K][K];
int dis[N];
int n;
void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tuopu()
{
	int hh = 0, tt = -1;
	for (int i = 1; i <= n; i++) {
		if (!d[i]) {
			q[++tt] = i;
		}
	}
	while (hh <= tt) {
		int t = q[hh++];
		for (int i = h[t]; ~i; i = ne[i]) {
			int j = e[i];
			if (--d[j] == 0) {
				q[++tt] = j;
			}
		}
	}
}


void dijkstra1()
{
	memset(dis, 0x3f, sizeof(dis));
	dis[1] = 0;
	for (int i = 0; i < n; i++) {
		int t = -1;
		for (int j = 1; j <= n; j++) {
			if (!st[j] && (t == -1 || dis[t] > dis[j])) {
				t = j;
			}
		}
		st[t] = 1;
		for (int j = 1; j <= n; j++) {
			dis[j] = min(dis[j], dis[t] + g[t][j]);
		}
	}
}


void dijkstra2()
{
	priority_queue<PII, vector<PII>, greater<PII>>heap;
	heap.push({ 0,1 });
	dis[1] = 0;
	while (heap.size()) {
		PII t = heap.top();
		heap.pop();
		int ver = t.y;
		int dist = t.x;
		if (st[ver])continue;
		st[ver] = 1;
		for (int i = h[ver]; ~i; i = ne[i]) {
			int j = e[i];
			if (dis[j] > dist + w[i]) {
				dis[j] = dist + w[i];
				heap.push({ dis[j],j });
			}
		}
	}
}
int main()
{
	
	return 0;
}